﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Spring08Lab2
{
    /// <summary>
    /// A node in the linked list
    /// </summary>
    public class LLNode
    {
        #region instance vars and properties
        private LLNode head;
        public LLNode Head
        {
            get { return head; }
            set { head = value; }
        }

        private LLNode tail;
        public LLNode Tail
        {
            get { return tail; }
            set { tail = value; }
        }

        private int data;
        public int Data
        {
            get { return data; }
            set { data = value; }
        }
        #endregion
        #region constructors
        public LLNode()
        {
            this.head = null;
            this.tail = null;
            this.data = 0;
        }
        public LLNode(int data)
        {
            this.data = data;
        }
        public LLNode(LLNode head, LLNode tail, int data)
        {
            this.head = head;
            this.tail = tail;
            this.data = data;
        }
        #endregion
    }

    /// <summary>
    /// A simple linked list
    /// </summary>
    public class LinkedList
    {
        #region instance vars and properties
        private LLNode head;
        public LLNode Head
        {
            get { return head; }
        }
        private LLNode tail;
        public LLNode Tail
        {
            get { return tail; }
        }
        #endregion
        #region constructors
        public LinkedList()
        {

        }
        public LinkedList(LLNode node)
        {
            this.head = node;
            this.tail = null;
        }
        public LinkedList(LLNode head, LLNode tail)
        {
            this.head = head;
            this.tail = tail;
        }
        #endregion
        #region operations
        /// <summary>
        /// This adds a node to the front of the 
        /// linked list.
        /// </summary>
        /// <param name="node">LLNode node to add</param>
        /// <example>
        /// LinkedList l1 = new LinkedList();
        /// LLNode n1 = new LLNode(null, null, 1);
        /// l1.AddToFront(n1);
        /// </example>
        /// <remarks>Author: Andrew Guyton</remarks>
        public void AddToFront(LLNode node)
        {
            // if the tail isn't set yet, 
            // and we go from having one node to two
            // set the tail pointer to the appropriate node
            if (this.tail == null && this.head != null)
            {
                this.tail = this.head;
            }

            // set the new head's tail to the current head
            node.Tail = this.head;

            // set the old head's head to the new head
            if (this.head != null)
            {
                this.head.Head = node;
            }

            // set the linked list's head to the new head
            this.head = node;
        }

        /// <summary>
        /// This removes a node from the front of the 
        /// linked list and returns it.
        /// </summary>
        /// <returns>the LLNode being removed</returns>
        /// <example>
        /// LinkedList l1 = new LinkedList();
        /// LLNode n1 = new LLNode(null, null, 1);
        /// l1.AddToFront(n1);
        /// int data = l1.RemoveFromFront()  // should return 1
        /// </example>
        /// <remarks>Author: Andrew Brown</remarks>
        public LLNode RemoveFromFront()
        {
            //checks to see if the list is empty
            if (this.head != null)
            {
                LLNode temp = this.head;

                //checks to see if the head being removed is the last node.
                if (this.head.Tail != null)
                {
                    //if there is more than one node, set new head
                    this.head = this.head.Tail;
                    this.head.Head = null;
                }
                else
                {
                    //if there was only one node, set head and tail to null
                    this.head = null;
                    this.tail = null;
                }
                return temp;
            }
            else
            {
                //if list was empty to begin with, return null
                return null;
            } 
        }

        /// <summary>
        /// This adds a node to the back of the 
        /// linked list.
        /// </summary>
        /// <param name="node">LLNode node to add</param>
        /// <example>
        /// LinkedList l1 = new LinkedList();
        /// LLNode n1 = new LLNode(null, null, 1);
        /// l1.AddToBack(n1);
        /// </example>
        /// <remarks>Author: Michael Derosa</remarks>
        public void AddToBack(LLNode node)
        {
            // set the new tail's tail to null
            node.Tail = null;
            
            //set the new tail's head to the old tail
            node.Head = this.tail;

            // set the old tail's tail to the new tail
            if (this.tail != null)
            {
                this.tail.Tail = node;
            }

            // set the linked list's tail to the new tail
            this.tail = node;
        }

        /// <summary>
        /// This removes a node from the back of the 
        /// linked list and returns it.
        /// </summary>
        /// <returns>the LLNode being removed</returns>
        /// <example>
        /// LinkedList l1 = new LinkedList();
        /// LLNode n1 = new LLNode(null, null, 1);
        /// l1.AddToBack(n1);
        /// LLNode back = l1.RemoveFromBack()  // should return 1
        /// </example>
        /// <remarks>Author: Steven Dalton</remarks>
        public LLNode RemoveFromBack()
        {
            LLNode ret = null;

            // check if it was a single element list
            if (this.head != null && this.tail == null)
            {
                ret = this.head;
                this.head = null;
            }
            // check that the list is not empty
            else if (this.tail != null)
            {
                // return the old tail
                ret = this.tail;

                // check if it was a single element list
                if (this.head == this.tail)
                {
                    //empty the list if single element list
                    this.tail = null;
                    this.head = null;
                }
                else
                {
                    // set the new tail to the old tail's head
                    this.tail = this.tail.Head;
                    // set tail to point to null
                    this.tail.Tail = null;
                }

            }

            return ret;
        }
        #endregion
    }
}
